2268. Кухонный робот

 

Роботы со временем становятся все популярнее. Сегодня их используют не только на больших заводах, но и в домашних условиях. Один программист вместе со своими друзьями решили создать своего собственного домашнего робота. Как Вы знаете, большинство программистов любит собираться на вечеринки и пить пиво. После ее завершения на столе остается множество пустых бутылок. Поэтому было решено создать робота, который будет способен собрать пустые бутылки со стола.

Стол представляет собой прямоугольник с длиной l и шириной w. Робот стартует с точки (xr, yr) и n бутылок находится в точках (xi, yi) (1 ≤ i ≤ n). Для того чтобы забрать бутылку, робот должен переместиться в точку где она расположена и взять ее, после чего отнести бутылку в некоторую точку на границе стола и отпустить ее. В любой момент времени робот может держать только одну бутылку, а отпускать ее только на границе стола.

Размеры бутылок и робота считайте пренебрежимо малыми (робот и бутылки являются точками). Роботу, держащему бутылку, можно передвигаться через точку, в которой находится другая бутылка.

Одной из подпрограмм робота является планирование маршрута. Вам следует написать программу, которая найдет маршрут минимальной длины, по которому робот соберет все бутылки.

 

Вход. Первая строка содержит два целых числа w и l (2 ≤ w, l ≤ 1000) – ширина и длина стола.

Вторая строка содержит количество бутылок на столе n (1 ≤ n ≤ 18). Каждая из следующих n строк содержит два целых числа xi и yi – координаты i-ой бутылки (0 < xi < w, 0 < yi < l). Никакие две бутылки не располагаются в одной точке.

Последняя строка содержит два целых числа xr и yr – координаты начального положения робота (0 < xr < w, 0 < yr < l). Робот не находится в одной точке ни с какой бутылкой.

 

Выход. Вывести длину кратчайшего пути, по которому робот соберет все бутылки. Ошибка точности вычислений не должна превышать 10-6.

 

Пример входа

Пример выхода

 
3 4
2
1 1
2 3

2 1

5.60555127546399

 

 

РЕШЕНИЕ

динамическое программирование - задача коммивояжера, NP полнота

 

Анализ алгоритма

Пусть A и B – две бутылки, которые последовательно будут собраны роботом со стола. Тогда после того как робот возьмет бутылку А, он должен ее выбросить на одной из четырех границ стола. Затем только он пойдет за бутылкой В. Найдем кратчайший путь робота от точки A(xi, yi) до B(xj, yj) с заходом на край стола.

Расстояние AK + KB = AK + KP = AP. Учитывая координаты точек A(xi, yi) и P(xj, -yj), получим

AP =  =

Расстояние AL + LB = AL + LQ = AQ. Абсцисса точки Q равна w + (w – xj) = 2w – xj. Учитывая координаты точек A(xi, yi) и Q(2w – xj, yj), получим

AQ =  

 

 

Расстояние AE + EB = AE + ET = AT. Учитывая координаты точек A(xi, yi) и T(-xj, yj), получим

AT =  =

Расстояние AD + DB = AD + DS = AS. Ордината точки S равна l + (l – yj) = 2l – yj. Учитывая координаты точек A(xi, yi) и S(xj, 2l – yj), получим

AS =  

 

Найдем наименьшее расстояние, необходимое для выбрасывания одной бутылки, находящейся в точке (xi, yi), за край стола. Оно равно минимуму из четырех отрезков:

min( xi, yi, w – xi, l – yi)

Это будет путь, который робот должен пройти чтобы выбросить последнюю бутылку.

 

Начальное положение робота и координаты бутылок заданы. Рассмотрим граф, нулевая вершина которого соответствует начальному положению робота, а остальные вершины соответствуют бутылкам. Расстояние между нулевой и остальными вершинами равно Евклидовому расстоянию между точками.  Расстояние между бутылками i и j равно минимальному пути, по которому можно пройти от бутылки i до бутылки j, побывав на кранице стола. Поскольку на столе имеется n бутылок, то граф будет содержать n + 1 вершину.

Далее следует найти в графе Гамильтонов путь минимальной длины. По окончанию, когда робот дойдет до последней бутылки, к общему результату еще следует прибавить путь, необходимый для выбрасывания этой бутылки за край стола. Искомый Гамильтонов путь ищем при помощи динамического программирования с масками с оценкой сложности O(n2 * 2n).

 

Пример

Начальное положение робота и положение бутылок приведены ниже.

Длина кратчайшего пути робота равна

1 +  + 1 = 2 +  ≈ 5.605

 

Реализация алгоритма

Объявим константу бесконечность INF и максимальное количество точек в Гамильтоновом пути MAX.

 

#define INF 1e18

#define MAX 20

 

Объявим массив dp, в котором будем хранить динамически пересчитываемые значения dp(S, i). Координаты бутылок храним в точках (xi, yi) (1 ≤ i ≤ n). Начальное положение робота храним в (x0, y0).

 

double dp[1 << MAX][MAX + 1];

double x[MAX], y[MAX], m[MAX][MAX];

 

Функция solve вычисляет значение dp(S, last), где множество S кодируется целым числом mask. При этом S \ {last} равно mask ^ (1<< last). Далее перебираем все i, i Î S \ {last} и ищем минимальное значение res среди dp(S \ {last}, i) + m[i][last]. Переменная res указывает на ячейку dp[mask][last], так что с изменением res изменяется и само значение dp[mask][last].

 

double solve(int mask, int last)

{

  double &res = dp[mask][last];

  if (res == INF)

  {

    mask ^= (1 << last);

    for (int i = 1; i < n; i++)

      if ((mask & (1 << i)) && (i != last))

        res = min(res, solve(mask, i) + m[i][last]);

  }

  return res;

}

 

Функция f возвращает кратчайшее расстояние от точки (x[i], y[i]) до края стола.

 

double f(int i)

{

  return min(min(x[i], y[i]), min(l - y[i], w - x[i]));

}

 

Функция dist возвращает расстояние между точками (x[i], y[i]) и (x[j], y[j]).

 

double dist(int i, int j)

{

  return sqrt((x[i] - x[j])*(x[i] - x[j]) +

              (y[i] - y[j])*(y[i] - y[j]));

}

 

Основная часть программы. Читаем размер стола w и l.

 

scanf("%d %d", &w, &l);

 

Читаем количество бутылок n и их координаты (x[i], y[i]).

 

scanf("%d", &n);

for (i = 0; i < n; i++)

  scanf("%lf %lf", &x[i + 1], &y[i + 1]);

 

Начальные координаты робота занесем в (x[0], y[0]).

 

scanf("%lf %lf", &x[0], &y[0]);

 

К n бутылкам добавим нулевую вершину – начальное положение робота. После увеличения на единицу n содержит количество вершин в графе. Вершины графа нумеруются 0, 1, …, n – 1.

 

n++;

 

Вычисляем попарные расстояния между бутылками. Расстояние между бутылками i и j равно минимальному пути, по которому можно пройти от бутылки i до бутылки j, побывав на кранице стола.

 

for (i = 1; i < n - 1; i++)

for (j = i + 1; j < n; j++)

  m[i][j] = m[j][i] =

    min(

  min(sqrt((x[i] + x[j])*(x[i] + x[j]) + (y[i] - y[j])*(y[i] - y[j])),

     sqrt((2 * w - x[i] - x[j])*(2 * w - x[i] - x[j]) +

          (y[i] - y[j])*(y[i] - y[j]))),

 min(sqrt((x[i] - x[j])*(x[i] - x[j]) + (y[i] + y[j])*(y[i] + y[j])),

     sqrt((x[i] - x[j])*(x[i] - x[j]) +

          (2 * l - y[i] - y[j])*(2 * l - y[i] - y[j])))

       );

 

Изначально значения dp(S, i) неизвестны, положим их равными плюс бесконечности.

 

for (i = 0; i < 1 << n; i++)

for (j = 0; j < n; j++)

  dp[i][j] = INF;

 

Множеству {0} соответствует маска 1, положим dp({0}, 0) = 0 (минимальный путь из нулевой вершины в нее же без посещения других вершин равен нулю). В переменной total храним искомую минимальную длину Гамильтонова пути.

 

dp[1][0] = 0; total = INF;

for (i = 1; i < n; i++) dp[1 | (1 << i)][i] = dist(0, i);

 

Находим гамильтонов путь минимальной длины. Значение 2n – 1 соответствует множеству {0, 1, 2, ..., n – 1}. Вычисляем минимум среди всех значений dp({0, 1, 2, ..., n – 1}, i) + f(i), 1 £ i < n. После вычисления минимальной длины Гамильтонова пути следует добавить расстояние, которое должен пройти робот для выбрасывания последней i-ой бутылки за границу стола – оно равно f(i).

 

for (i = 1; i < n; i++)

  total = min(total, solve((1 << n) - 1, i) + f(i));

 

Выводим искомую минимальную длину.

 

printf("%.6lf\n", total);